package com.algorithmicTest1;

public class Quicksort {
    public static void main(String[] args) {
        //目的：实现快速排序的代码：
        //1：创建一个打乱的数组
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quickSort(arr,0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }

    }
    //2:创建一个方法能够实现快速排序
    //需要3个参数，一个起始索引的参数，一个结束索引的参数，还有数组
    public static void quickSort(int[]arr,int i, int j){
        //先将起始索引第一个元素作为参数：
        int start = i;
        int end = j;
        int index = arr[i];
        if(start >= end){
            return;
        }


        while (start!=end){
            while(true){
                if(end <= start || arr[end] < index){
                    break;
                }
                end--;
            }

            while (true){
                if(start>=end || arr[start] > index){
                    break;
                }
                start++;
            }
            //交换数据：
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //确认基数位置：
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        //确定6左边的范围
        quickSort(arr,i,start-1);
        //确定6右边的范围
        quickSort(arr,start+1,j);


    }

}
